package 中等.链表;

import util.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/reorder-list
 */
public class 重排链表_143 {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        reorderList(node1);

    }

    /**
     * 数组+双指针模拟
     */
    public static void reorderList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        head = new ListNode(0);

        ListNode curNode = head;
        int left = 0, right = list.size() - 1;
        while (left < right) {
            curNode.next = list.get(left);
            curNode = curNode.next;
            curNode.next = list.get(right);
            curNode = curNode.next;

            left++;
            right--;
        }

        // 需要注意将最后一个节点置空，防止链表成环
        // 为偶数时 curNode 就是最后一个节点
        curNode.next = null;
        // 为奇数时 还要加上 left 节点
        if (left == right) {
            ListNode lastNode = list.get(left);
            lastNode.next = null;
            curNode.next = lastNode;
        }
        head = head.next;
    }

}
